package com.asia.algorithmcode.array;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

/**
 * 128、最长连续序列
 */
public class LongestConsecutive {

    public static void main(String[] args) {
        int[] arr = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
        System.out.println(new LongestConsecutive().longestConsecutive_2(arr));
    }


    /**
     * 使用哈希表，将遍历检索是否存在下一个连续的数字的复杂度降为了O(1)，加上了对前一个数字的检索，整体复杂度降到了O(N)
     * 但是实际执行效果似乎不如第一个方法
     * @param nums
     * @return
     */
    public int longestConsecutive_2(int[] nums) {
        if (nums.length <= 1) return nums.length;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int max = 0;
        for (Integer num : set) {
            if (!set.contains(num - 1)) {
                int cur = num;
                int longest = 1;
                while (set.contains(cur + 1)) {
                    cur++;
                    longest++;
                }
                max = Math.max(max, longest);
            }
        }
        return max;
    }

    /**
     * 方法1：先用nlogn的排序，然后用O(n)的时间进行遍历
     *
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {
        if (nums.length <= 1) return nums.length;
        Arrays.sort(nums);
        int max = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] + 1 == nums[i]) {
                count++;
            } else if (nums[i - 1] != nums[i]) {
                count = 1;
            }
            max = Math.max(max, count);
        }
        return max;
    }

}
